class QuickSort {
  constructor() {
    let that = this;
  }
  quickSort (arr, startIndex, endIndex) {
    // 递归结束条件：startIndex大等于endIndex的时候
    if (startIndex >= endIndex) {
      return
    }
    // 得到基准元素位置
    let pivotIndex = this.partition(arr, startIndex, endIndex);
    // 得到基准元素位置，分成两部分递归排序
    this.quickSort(arr, startIndex, pivotIndex - 1)
    this.quickSort(arr, pivotIndex + 1, endIndex)
  }
  partition (arr, startIndex, endIndex) {
    let pivot = arr[startIndex];
    let mark = startIndex;
    for (let i = startIndex + 1; i <= endIndex; i++) {
      if (arr[i] < pivot) {
        mark++;
        let p = arr[mark];
        arr[mark] = arr[i];
        arr[i] = p;
      }
    }
    arr[startIndex] = arr[mark];
    arr[mark] = pivot;
    return mark;
  }
}
let arr = [4, 4, 6, 5, 3, 2, 8, 1];
let quick = new QuickSort();
quick.quickSort(arr, 0, arr.length - 1);
console.log(arr);